package top.ezzz.base;

import cn.hutool.core.util.StrUtil;
import cn.hutool.json.JSONUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class NQueens {

    static List<List<String[]>> res = new ArrayList<>();

    public static void main(String[] args) {
        List<List<String[]>> lists = solveNQueens(8);
        System.out.println(JSONUtil.toJsonStr(lists));
    }

    public static List<List<String[]>> solveNQueens(int n) {
        ArrayList<String[]> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            board.add(StrUtil.repeat(".", n).split(""));
        }
        backtrack(board, 0);
        return res;
    }

    /**
     * 一歌结果就结束
     *
     * @param board
     * @param row
     * @return
     */
    private static boolean backtrackOne(List<String[]> board, int row) {
        if (row == board.size()) {
            res.add(board);
            return true;
        }
        int n = board.get(row).length;
        for (int col = 0; col < n; col++) {
            // 出发结束条件
            if (!isValid(board, row, col)) {
                continue;
            }
            //做选择
            board.get(row)[col] = "Q";
            //进入下一行决策
            //backtrack(board, row + 1);
            if (backtrackOne(board, row + 1)) {
                // 一次结果就返回
                return true;
            }
            //撤销选择
            board.get(row)[col] = ".";
        }
        return false;
    }

    private static void backtrack(List<String[]> board, int row) {
        if (row == board.size()) {
            res.add(new ArrayList<>(board));
            return;
        }
        int n = board.get(row).length;
        for (int col = 0; col < n; col++) {
            // 出发结束条件
            if (!isValid(board, row, col)) {
                continue;
            }
            //做选择
            board.get(row)[col] = "Q";
            //进入下一行决策
            backtrack(board, row + 1);
            //撤销选择
            board.get(row)[col] = ".";
        }

    }

    /**
     * 判断 当前行列元素board[row][col]是否可以放置皇后
     *
     * @param board
     * @param row
     * @param col
     * @return
     */
    private static boolean isValid(List<String[]> board, int row, int col) {
        int n = board.size();
        // 列上是否有皇后
        for (int i = 0; i < row; i++) {
            if ("Q".equals(board.get(i)[row])) {
                return false;
            }
        }
        //  右上方
        for (int i = row - 1, j = col + 1;
             i >= 0 && j < n;
             i--, j++) {
            if ("Q".equals(board.get(i)[j])) {
                return false;
            }
        }
        // 左上方
        for (int i = row - 1, j = col - 1;
             i >= 0 && j >= 0;
             i--, j--) {
            if ("Q".equals(board.get(i)[j])) {
                return false;
            }
        }
        return true;
    }
}
